% !TeX spellcheck = fr-moderne
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}
\usepackage{pgfplots}
\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

%\setbeamertemplate{bibliography item}{[\theenumiv]}
\setbeamertemplate{bibliography item}[text]

\setbeamertemplate{footline}
{
  \leavevmode%
  \hbox{%
  \begin{beamercolorbox}[wd=.4\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertshortauthor (\insertshortinstitute)
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.6\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
    \usebeamerfont{title in head/foot}\insertshorttitle\hspace*{3em}
    \insertframenumber{} / \inserttotalframenumber\hspace*{1ex}
  \end{beamercolorbox}}%
  \vskip0pt%
}

\usepackage[variablett]{lmodern}
\lstset{ %
  backgroundcolor=\color{white},
  language=C++,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
  captionpos=b,
  commentstyle=\color{green},
  deletekeywords={...},
  extendedchars=true,
  frame=single,
  keepspaces=true,                 
  keywordstyle=\color{blue},
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,
  numbersep=5pt,
  numberstyle=\tiny\color{black},
  rulecolor=\color{black},
  showstringspaces=false,
  stepnumber=1,
  title=\lstname,
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title{Techniques de consistance d'ordre supérieur} % The short title appears at the bottom of every slide, the full title is only on the title page
%\titlegraphic{\includegraphics[width=1.5cm]{./images/UCL_logo.png}}

\author[KHONG Minh Thanh ]{
Etudiant: KHONG Minh Thanh\\
Superviseur: Yves Deville
}

\vspace{3cm}

\institute[UCL]{
Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM) \\ Université catholique de Louvain
}

\date{October 28, 2014}

\begin{document}
\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%------------------------------------------------
\section{Motivation}
%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
\begin{itemize}
\item Les problèmes combinatoires sont omniprésents dans les industries ainsi que dans les services, tels que la planification, le routage de véhicules, le réseaux,\dots
%{\centering
%\includegraphics[width=3cm]{./images/planning_problem.png}
%}
\item Ces problèmes peuvent se représenter comme des problèmes de satisfaction de contraintes (optimisation) (CSP).
\item Un CSP est défini par un ensemble de variables (qui ont un domaine fini) et un ensemble de contraintes que doit satisfaire la solution.
\item La programmation par contraintes permet de résoudre efficacement les CSP.  Elle combine deux étapes : \textit{propagation} et \textit{recherche}.

\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
\begin{columns}[T] % align columns
\begin{column}{.60\textwidth}
\footnotesize
La recherche
\begin{itemize}
\item La recherche assigne des valeurs aux variables.
%\item L'assignation partielle doit satisfaire les contraintes portantes sur les variables assignées. 
%\item Si aucune valeur n'est trouvée, la branche de recherche est échouée.
%\item L'espace de recherche est considérée comme un arbre de recherche.
\item La taille de l'espace de recherche est exponentielle. 
\end{itemize}
La propagation

\begin{itemize}
\item La propagation permet de réduire l'espace de recherche sans enlever de solutions. Elle enlève des valeurs impossibles du domaine des variables.
\item La propagation se base sur une propriété de consistance.
\item La consistance de domaine (DC) est la propriété la plus utilisée pour la propagation.
%\item La propagation détecte également les échecs, et termine les branches de l'arbre de recherche, économise l'exploration inutile de l'espace de recherche.
\end{itemize}
\end{column}%
\begin{column}{.38\textwidth}

\begin{figure}
\includegraphics[width=4cm]{./images/4_queen_backtrack.png}
\caption{ \scriptsize{L'arbre de recherche sans propagation}}

\includegraphics[width=3.8cm]{./images/4_queens_forward.png}
\caption{\scriptsize{L'arbre de recherche avec la propagation}}
\end{figure}
\end{column}%
\end{columns}
\end{frame}

%------------------------------------------------
\begin{frame}{Motivation}

La consistance de domaine (DC) considère chaque contrainte localement et enlève les valeurs impossibles pour cette contraintes.

Exemple:

\begin{itemize}
\item Etant donné un CSP : \\
 $D(x)= D(y)= \{1,2,3,4,5\}$ et $c(x,y)= x \leq y -2$. 
 \includegraphics[width=10cm]{./images/DC_ex.png}
\item Cette contrainte n'est pas DC parce que $(x,4), (x,5), (y,1), (y,2)$ ne satisfont pas $c(x,y)$ (n'ont pas de DC-support).
\item Appliquer la consistance DC pour cette contrainte, on obtient : $D(x)=\{1,2,3\}$ et $D(y)= \{3,4,5\}$.
\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
\begin{itemize}
\item La puissance d’élagage DC n'est pas assez forte pour résoudre certains problèmes complexes.
\item Intérêt de techniques de consistance d'ordre supérieur pour les résoudre.
\item Une consistance est d'ordre supérieur lorsqu'elle permet d'enlever plus de valeurs que la consistance de domaine (DC).
\item Une consistance d'ordre supérieur considère en même temps plus d'une contrainte, tout en évitant l'explosion combinatoire.
\end{itemize}

\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}

\begin{itemize}
\item Etant donné un CSP : \\
$D(x) = D(y) = D(z) = \{1, 2\}$ et $c_1 : x \neq y, c_2 : y \neq z, c_3 : x \neq z$

\begin{figure}[ht]
\centering
\includegraphics[width=3.3cm]{./images/DC_no_solution.jpeg}
%\caption{Un exemple d'un CSP qui est DC mais il n'y a pas de solution.}
\end{figure}


\item Le CSP est DC car pour chaque contrainte prise individuellement, chaque valeur peut satisfaire cette contrainte, par exemple : pour  $(x, 1)$, on a $(y, 2)$ pour $c_1$ et $(z, 2)$ pour $c_3$. \\
Mais ce CSP n'a pas de solution.
\item Si on applique une consistance d'ordre supérieur, une telle inconsistance peut être directement détectée, sans effectuer de recherche.
\end{itemize}

\end{frame}


%------------------------------------------------
\section{Etat de l'art}
%------------------------------------------------
\begin{frame}
\frametitle{Etat de l'art}
Exemples de consistances d'ordre supérieure pour les CSP (dont les contraintes sont) binaires,
\begin{itemize}
\item Consistance basée sur les triangles de contraintes
	\begin{itemize}
	\item Restricted Path Consistency (RPC) \cite{Berlandier1995Improving}
	\item Path Inverse Consistency (PIC) \cite{Freuder1996Neighborhood}
	\item Max Restricted Path consistency (MaxRPC) \cite{Debruyne1997From}
	\end{itemize}
\item Consistance basée sur le voisinage de la contrainte
	\begin{itemize}
	\item Neighborhood Inverse Consistency (NIC) \cite{Freuder1996Neighborhood}
	\end{itemize}
\item Consistance basée sur l'assignation hypothétique d'une valeur à une variable
	\begin{itemize}
	\item Singleton Domain Consistency (SDC) \cite{Debruyne1997bSome}
	\end{itemize}
\end{itemize}
\end{frame}

%%------------------------------------------------
%\begin{frame}
%\frametitle{Etat de l'art}
%Exemples de consistances d'ordre supérieure pour les CSP (dont les contraintes sont) binaires,
%\begin{itemize}
%\item Restricted Path Consistency (RPC) \cite{Berlandier1995Improving}
%% : il assure si une valeur a une seul moyen pour satisfaire la contrainte, alors elle peut étendre aux triangle contraintes.
%\\ basé sur les triangles de contraintes
%\item Path Inverse Consistency (PIC) \cite{Freuder1996Neighborhood}
%% : il assure que chaque valeur peut étendre aux triangle contraintes.
%\\ basé sur les triangles de contraintes
%\item Max Restricted Path consistency (MaxRPC) \cite{Debruyne1997From}
%% : il assure que chaque valeur a au moins un support qui peut étendre aux n'importe triangle contraintes.
%\\ basé sur les triangles de contraintes
%\item Neighborhood Inverse Consistency (NIC) \cite{Freuder1996Neighborhood}
%%% : il assure que chaque valeur dans le domaine d'une variable peut étendre aux tous les voisinages de cette contraintes.
%\\ basé sur le voisinage de la contrainte
%\item Singleton Domain Consistency (SDC) \cite{Debruyne1997bSome}
%%% : quand on assigne une valeur à une variable, après avoir appliqué un algorithme pour DC, si le résultat est échec, alors cette valeur est enlevée.
%\\ basé sur l'assignation hypothétique d'une valeur à une variable
%\end{itemize}
%\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Etat de l'art}
\begin{itemize}
\item Pour les CSP non-binaires
	\begin{itemize}
	\item Restricted Pairwise Consistency (RPWC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
	\item relational Path Inverse Consistency  (rPIC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
	\item Max Restricted Pairwise Consistency (MaxRPWC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
	\end{itemize}

\item Les consistances pour les CSP non-binaires sont moins étudiées que celles pour les CSP binaires.

\item Les solveurs existants (Gecode, JaCoP, Google or-tools, Choco, IlogCP, Comet, Oscar ou Abscon) n'ont pas encore intégré ces consistances.  Une intégration nécessite de généraliser les mécanismes de base de propagation des solveurs.

\end{itemize}


\end{frame}

%------------------------------------------------
\section{Résultats du mémoire de fin d’études}
%------------------------------------------------
%------------------------------------------------
\begin{frame}
\frametitle{Résultats du mémoire de fin d’études}
\begin{itemize}
\item Ingénieur en Informatique et Mathématiques appliquées
	à l'Institut Polytechnique de Hanoï, Vietnam (2006-2011)
\item Master en Informatique à l’Institut de la Francophonie pour l’Informatique au Vietnam (2012-2014)
	\begin{itemize}
	\item Master 1 : Etudes générales
	\item Master 2 : Etudes spécialisées, option Systèmes Intelligents \& Multimédia (double diplômation avec l'Université de La Rochelle)
	\end{itemize}
\item Stage de fin d’études de 6 mois au département d’Ingénierie Informatique d’UCL (avril à octobre 2014)
	\begin{itemize}
	\item Sujet du stage : "Beyond domain consistency"
	\end{itemize}
\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Résultats du mémoire de fin d’études}
Nous avons : 
\begin{itemize}
\item Etudié les consistances d'ordre supérieur existantes.
\item Intégré les algorithmes pour certaines de ces consistances dans le solveur de programmation par constraintes  Abscon.
\item Experimenté ces algorithmes.
\end{itemize}
\end{frame}

%------------------------------------------------
\section{Objectif du projet}
%------------------------------------------------
\begin{frame}
\frametitle{Objectif du projet}
Nous allons :
\begin{itemize}
\item Développer de nouvelles techniques de consistance d'ordre supérieur dans le but d'accélérer la résolution de problèmes combinatoires complexes.
\item Envisager une combinaison des techniques de consistances existantes et nouvelles.
\item Développer différents algorithmes réalisant ces consistances, et les intégrer dans un solveur existant (Abscon), et les expérimenter sur des problèmes complexes.
\end{itemize}

\end{frame}


%------------------------------------------------
\section{Plan de travail}
%------------------------------------------------
\begin{frame}
\frametitle{Plan de travail}
\begin{itemize}
\item WP1. Etat de l'art, analyse et étude les techniques existantes de consistance d'ordre supérieur.
\item WP2. Introduction et définition de nouvelles consistances d'ordre supérieur.
\item WP3. Combinaison de différentes consistances d'ordre supérieur.
\item WP4. Conception et mis en œuvre des abstractions de calcul nécessaires.
\item WP5. Implémentation des consistances d'ordre supérieur dans un solveur.
\item WP6. Expérimentation et d'analyse.
\item WP7. Rédaction et publication.
\end{itemize}
\end{frame}


%------------------------------------------------
\section{Environnement de recherche}
%------------------------------------------------
\begin{frame}
\frametitle{Environnement de recherche}
\begin{itemize}
\item  Institute for Information and Communication Technologies, Electronics and Applied
Mathematics (ICTEAM) est un institut de recherche de l'Université catholique de Louvain.
   \begin{itemize}
   \item ICTEAM possède 50 professeurs et plus de 200 chercheurs.
   \end{itemize}
\item Le groupe de recherche des contraintes "beCool" dirigé par le Professeur Yves Deville, un expert en programmation par contraintes et en techniques de consistance.
%\item Le groupe développe des travaux théoriques et de prototypage, afin de valider leurs résultats sur des problèmes réels.
\item La thèse sera co-supervisée par le Professeur Christophe Lecoutre, un expert international en programmation par contraintes, Centre de Recherche en Informatique de Lens, Université d'Artois.  Il est l'auteur principal du système Abscon.
%\item Christophe Lecoutre est un expert international en programmation par contraintes, et plus particulièrement dans les techniques de consistance et d'algorithmes.
\end{itemize}


\end{frame}


%------------------------------------------------
\section{Conclusion}
%------------------------------------------------
\begin{frame}
\frametitle{Conclusion}
\begin{itemize}
\item La consistance d'ordre supérieur est prometteuse pour résoudre les problèmes combinatoires complexes.
\item Les premiers résultats de notre approche sont positifs.
\item Les techniques de consistance d'ordre supérieur seront développées et mises en œuvre dans un solveur existant (Abscon).
\item Nous testerons notre approche sur des problèmes réels complexes telles que la planification, le routage de véhicules.
\item Ce travail sera supervisé par deux spécialistes des techniques de consistance : Yves Deville (UCL) et Christophe Lecoutre (Univ. Artois).
\end{itemize}

\end{frame}

%%------------------------------------------------
%
\begin{frame}
\Huge{\centerline{Merci de votre attention !}}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\scriptsize
\bibitem{Stergiou2006Inverse} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{Berlandier1995Improving} Berlandier, P. "Improving domain filtering using restricted path consistency." Artificial Intelligence for Applications, 1995. Proceedings., 11th Conference on. IEEE, 1995.

\bibitem{Freuder1996Neighborhood} Freuder, Eugene C., and Charles D. Elfe. "Neighborhood inverse consistency preprocessing." AAAI/IAAI, Vol. 1. 1996.

\bibitem{Debruyne1997From} Debruyne, Romuald, and Christian Bessiere. "From restricted path consistency to max-restricted path consistency." Principles and Practice of Constraint Programming-CP97. Springer Berlin Heidelberg, 1997. 312-326.

\bibitem{Stergiou2006Inverse} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{Bessiere2008Domain} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.

\bibitem{Debruyne1997bSome} Debruyne, Romuald, and Christian Bessiere. "Some practicable filtering techniques for the constraint satisfaction problem." In Proceedings of IJCAI’97. 1997.
%\bibitem{Lecoutre2013Constraint} Lecoutre, Christophe. Constraint Networks: Targeting Simplicity for Techniques and Algorithms. John Wiley \& Sons, 2013.

\end{thebibliography}
}
\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 